package com.rikai.Rikai;

import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.RandomAccessFile;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.Vector;
import java.util.zip.DataFormatException;
import java.util.zip.Deflater;
import java.util.zip.Inflater;

import android.util.Log;


public class Data {
  public final static int PAGE_SIZE = 8 * 1024;	
  public final static int DEFLATE_MAX_HEADER = 1024*4; // total guess
  Data() {
  }

  public static int compressBytes(byte[] bytes, byte[] into) {
    return compressBytes(bytes, 0, bytes.length, into);
  }
  public static int compressBytes(byte[] bytes, int offset, int length, byte[] into) {
    Deflater deflater = new Deflater();
    deflater.setInput(bytes,offset,length);
    deflater.finish();
    int sz = deflater.deflate(into);
    if (!deflater.finished()) {
      throw new RuntimeException("compressBytes() into is too small");
    }
    //Log.e("RIKAI","Compressed " + (length-offset) + " bytes into " + sz);
    return sz;
  }
  public static byte[] decompressBytes(byte[] compressedInput) {
    return decompressBytes(compressedInput, 0, compressedInput.length);
  }
  private static byte[] dbbuf;
  private static byte[] copyOf(byte[] ba, int len) {
    int ml = Math.min(len,ba.length);
    byte[] ret = new byte[ml];
    for (int i=0; i<ml; ++i) {
      ret[i] = ba[i];
    }
    return ret;
  }
  public static synchronized byte[] decompressBytes(byte[] compressedInput, int offset, int length) {
    Inflater decompressor = new Inflater();
    decompressor.setInput(compressedInput, offset, length);

    if (dbbuf == null) { 
      dbbuf = new byte[PAGE_SIZE*10];
    }
    try {
      int sz = decompressor.inflate(dbbuf);
      if (!decompressor.finished()) {
        throw new RuntimeException("decompressBytes too big");
      } else {
        return copyOf(dbbuf,sz);
      }
    } catch (DataFormatException e) {
      throw new RuntimeException("DataFormatException " + e.toString());
    }
  }
  public class CompressedReader {
	  TreeMap<Long,Long> offsetMap; // map from decompressed to compressed
	  public RandomAccessFile f;
    public boolean eof;
	  long dOffset;
    long startOfIndex;
    Map<Long,byte[]> compOffsetToBufCache;
    Vector<Long> allOffsets;
    
    Map<byte[], Vector<byte[]> > binSearchCache;
    Vector<byte[]> blockKeyCache;

	  CompressedReader(String filename) throws FileNotFoundException,IOException {
		  f = new RandomAccessFile(filename,"r");
		  long length = f.length();
		  f.seek(length - Long.SIZE/8);
		  final long offsetTableSize = f.readLong();
		  offsetMap = new TreeMap<Long,Long>();
      allOffsets = new Vector<Long>();
      blockKeyCache = new Vector<byte[]>();
      startOfIndex = length - Long.SIZE/8 - offsetTableSize * Long.SIZE/8;
		  f.seek(startOfIndex);
      offsetMap.put(0L,0L);
      allOffsets.addElement(0L);
      blockKeyCache.addElement(null);
		  for (long l=0; l < offsetTableSize; l+=2) {
			  long key = f.readLong();
			  long val = f.readLong();
			  offsetMap.put(key,val);
        allOffsets.addElement(key);
        blockKeyCache.addElement(null);
		  }
		  dOffset=0;
      compOffsetToBufCache = new LinkedHashMap<Long,byte[]>(1, .75F, true) {
        @Override
          protected boolean removeEldestEntry(Map.Entry<Long,byte[]> eldest) { return size() > 10; }
      };
      binSearchCache = new LinkedHashMap<byte[], Vector<byte[]> >(1, .75F, true) {
        @Override
          protected boolean removeEldestEntry(Map.Entry<byte[],Vector<byte[]> > eldest) { return size() > 20; }
      };
      // start thread to start to fill-in blockKeyCache
      new Thread(new Runnable() {
        public void run() {
          for (int i=0; i<allOffsets.size(); i+=1) {
            synchronized(blockKeyCache) {
              if (blockKeyCache.elementAt(i) != null) continue;
            }
            DecompBlock block = null;
            try { block = fetchBlockAt(allOffsets.elementAt(i), false); } catch (Throwable t) { continue; }
            byte[] buf = block.data;
            int size = block.data.length;
            int offset = 0;
            if (i!=0) {
              while (offset < size && buf[offset] != '\n') offset += 1;
              while (offset < size && buf[offset] == '\n') offset += 1;
            }
            if (offset < size) {
              int nnl = offset; while (nnl < buf.length && buf[nnl] != '\n') { nnl +=1; }
              if (nnl > offset && nnl < buf.length && buf[nnl] == '\n') {
                synchronized(blockKeyCache) {
                  blockKeyCache.setElementAt(copyOf(buf,nnl+1),i);
                }
              }
            }
          }
        }
      }).start();
	  }
	  public void close() throws IOException {
		  if (f!=null) f.close(); f = null;
		  if (offsetMap != null) offsetMap = null;
	  }
    public void seek(long l) {
      dOffset = l;
      eof = false;
    }
    public long tell() {
      return dOffset;
    }
    public long size() {
      return offsetMap.lastKey();
    }
	  public int read(byte[] buf) throws IOException {
		  return read(buf,0,buf.length);
	  }
    class DecompBlock {
      byte[] data;
      long offset;
      long coffset;
    }
    private byte[] cBuf;
    synchronized DecompBlock fetchBlockAt(long l, boolean setCache) throws IOException {
      SortedMap<Long,Long> before = offsetMap.headMap(l+1); // can include offset
      SortedMap<Long,Long> after = offsetMap.tailMap(l+1);  // cannot include offset
      long blockCompressedOffset=0;
      long blockDecompressedOffset=0;
      if (!before.isEmpty()) {
        blockDecompressedOffset = before.lastKey();
        blockCompressedOffset = before.get(blockDecompressedOffset);
      }
      long blockCompressedEnd = startOfIndex;
      if (!after.isEmpty()) {
        blockCompressedEnd = after.get(after.firstKey());
      }
      // ok, now we have the right block.. Read it in and decompress it
      long compressedBlockSize = blockCompressedEnd - blockCompressedOffset;
      byte[] dcBuf;
      if (compressedBlockSize==0) {
        dcBuf = new byte[0];
      } else if (compOffsetToBufCache.containsKey(blockCompressedOffset)) {
        dcBuf = compOffsetToBufCache.get(blockCompressedOffset);
      } else {
        if (cBuf == null) { cBuf = new byte[PAGE_SIZE + DEFLATE_MAX_HEADER]; }
        f.seek(blockCompressedOffset);
        int cLen = f.read(cBuf,0,(int)compressedBlockSize);
        if (cLen != compressedBlockSize) {
          throw new RuntimeException("Read buffer length not what I expected");
        }
        dcBuf = decompressBytes(cBuf,0,(int)compressedBlockSize);
        if (setCache) {
          compOffsetToBufCache.put(blockCompressedOffset, dcBuf);
        }
      }
      DecompBlock ret = new DecompBlock();
      ret.data = dcBuf;
      ret.offset = blockDecompressedOffset;
      ret.coffset = blockCompressedOffset;
      //Log.e("RIKAI","Decompressed " + compressedBlockSize + " bytes to " + ret.data.length);

      return ret;
    }
	  public int read(byte[] buf, int offset, int length) throws IOException {
      if (eof) return 0;
      int minLength = Math.min(buf.length - offset,length);
      int readLength = 0;
      while (readLength < minLength) {
        DecompBlock db = fetchBlockAt(dOffset, true);
        byte[] dcBuf = db.data;
        int i = (int)(dOffset - db.offset); // index to start copying
        if (i>=dcBuf.length) {
          eof = true;
          return readLength;
        }
        while (i<dcBuf.length && readLength < minLength) {
          buf[readLength + offset] = dcBuf[i];
          readLength++;
          i++;
        }
      }
      return readLength;
	  }

    public int compare(byte[] b1, int o1, byte[] b2, int o2) {
      return compare(b1,o1,b2,o2,Integer.MAX_VALUE);
    }
    public int compare(byte[] b1, int o1, byte[] b2, int o2, int maxlen) {
      int i;
      int count=0;
      for (i=0; count < maxlen && i < b1.length - o1 && i < b2.length - o2; i+=1) {
        if ((b1[o1 + i] & 0xFF) < (b2[o2 + i] & 0xFF)) return -1;
        else if ((b1[o1 + i] & 0xFF) > (b2[o2 + i] & 0xFF)) return 1;
        count += 1;
      }
      if (count == maxlen) return 0;
      if (i == b1.length - o1) {
        if (i == b2.length - o2) return 0;
        else return -1;
      } else return 1;
    }
    private byte[] copyOf(byte[] ba, int len) {
      int ml = Math.min(len,ba.length);
      byte[] ret = new byte[ml];
      for (int i=0; i<ml; ++i) {
        ret[i] = ba[i];
      }
      return ret;
    }
    public boolean startsWith(byte[] val, byte[] key) {
      if (val.length < key.length) return false;
      for (int i=0; i<key.length; i+=1) 
        if (key[i] != val[i]) return false;
      return true;
    }
    public Vector<byte[]> binSearch(byte[] key) {
       synchronized(blockKeyCache) {
         if (binSearchCache.containsKey(key)) {
           return binSearchCache.get(key);
         }
         Vector<byte[]> ret = new Vector<byte[]>();
         try {	
           int bBlock = 0;
           int eBlock = allOffsets.size();
           byte[] buf = null;
           int offset = 0;
           long bestOffset = 0;
           while (eBlock - bBlock > 1) {
             int mid = (bBlock + eBlock) / 2;
             if (mid == eBlock) { // fallen off end
               return ret;
             }
             offset = 0;
             int size = 0;
             boolean setCache = false;
             synchronized (blockKeyCache) {
               if (false || (buf = blockKeyCache.elementAt(mid)) == null) {
                 DecompBlock block = fetchBlockAt(allOffsets.elementAt(mid), true);
                 buf = block.data;
                 size = block.data.length;
                 setCache = true;
               } else {
                 size = buf.length;
               }
             }

             if (mid != 0) {
               int sOffset = offset;
               while (offset < size && buf[offset] != '\n') offset += 1;
               while (offset < size && buf[offset] == '\n') offset += 1;
               if (offset >= size) {
                 Log.e("RIKAI","Cannot find newline at " + mid + ", end==" + eBlock + ", started at "+ sOffset + ", key = " + new String(key, "EUC-JP") + ", blen = " + buf.length);
                 //Log.e("RIKAI","block == " + new String(buf,"EUC-JP"));
                 return ret;
               } else {
                 //Log.e("RIKAI", "blen == " + buf.length);
               }
             }
             int nnl = offset; while (nnl < buf.length && buf[nnl] != '\n') { nnl +=1; }
             if (setCache && nnl > offset && nnl < buf.length) synchronized(blockKeyCache) {
               blockKeyCache.setElementAt(copyOf(buf,nnl + 1),mid);
             }
             int c = compare(key,0,buf,offset);
             if (c>=0) {
               bBlock = mid;
               bestOffset = offset + allOffsets.elementAt(mid);
             } else {
               eBlock = mid;
             }
           }
           { // search the block itself
             DecompBlock block = fetchBlockAt(bestOffset, true);
             byte[] fBuf = block.data;
             if (fBuf.length==0) return null; // last block
             int begp = (int)(bestOffset - block.offset); // we already know the first line's start
             // fetch last line in block and make sure we're in it. Otherwise we have the nasty intra-block case
             int endp = fBuf.length-1;
             while (endp > 0 && fBuf[endp] != '\n') endp-=1; // last endline
             int lastNL = endp;
             if (endp > 0) endp--;
             while (endp > 1 && fBuf[endp-1] != '\n') endp-=1; // backup to start of last full line
             if (compare(key,0,fBuf,endp) >=0) { // ugh.. Well, we know we have it from lastNL
               DecompBlock nextBlock = fetchBlockAt(block.offset + fBuf.length, true);
               byte[] checkBorder = new byte[fBuf.length - lastNL + 1024];
               for (int i=lastNL+1; i<fBuf.length; ++i) { checkBorder[i-lastNL-1] = fBuf[i]; }
               for (int i=0; i < nextBlock.data.length && nextBlock.data[i]!='\n'; ++i) {
                 checkBorder[fBuf.length-lastNL-1 + i] = nextBlock.data[i];
               }
               if (startsWith(checkBorder,key)) {
                 ret.addElement(checkBorder);
               }
               // because this was a partial line, we could still match the start of the next
               fBuf = nextBlock.data;
               begp = 0;
               while (begp < fBuf.length && fBuf[begp] != '\n') begp+=1; // first newline
               if (begp < fBuf.length) begp+=1;
               endp = fBuf.length-1;
               while (endp > 0 && fBuf[endp] != '\n') endp-=1; // last endline
               if (begp == fBuf.length || endp == 0) return ret;
             }
             // if we're here the answer is within this block. Pointers always point to start of lines
             while (endp > begp) {
               int midp = (endp + begp)/2;
               while (midp > begp && fBuf[midp-1]!='\n') midp--;
               if (compare(key,0,fBuf,midp)<=0) {
                 endp = midp;
               } else {
                 if (begp==midp) {
                   while (fBuf[midp] !='\n' && midp < endp) midp+=1;
                   if (midp < endp) midp+=1;
                   begp = midp;
                 } else {
                   begp = midp;
                 }
               }
             }
             while (begp < fBuf.length) {
               int nl = begp;
               while (nl < fBuf.length && fBuf[nl] != '\n') { nl+=1; }
               if (nl >= fBuf.length) return ret;
               byte[] val = new byte[nl - begp];
               for (int i=0; i<val.length; ++i) { val[i] = fBuf[i + begp]; }
               if (startsWith(val, key)) {
                 //Log.e("RIKAI","In binsearch add element " + val);
                 ret.addElement(val);
                 begp = nl + 1;
               } else break;
             }
           }
           byte[] keycopy = key.clone();
           binSearchCache.put(keycopy,ret);
           return ret;
         } catch (IOException e) {
           return ret;
         }
       }
    }
  }
  public CompressedReader getCompressedReader(String name) throws IOException, FileNotFoundException {
    return new CompressedReader(name);
  }
  public static void compressStream(InputStream is, String outfile) {
	try {
	    RandomAccessFile os = new RandomAccessFile(outfile,"rw");
      byte[] inbuf = new byte[PAGE_SIZE];
      int byteoff = 0;
      byte[] outbuf = new byte[PAGE_SIZE+DEFLATE_MAX_HEADER];
      int i;
      Vector<Long> offsets = new Vector<Long>();
      long decompOffset = 0;
      try {
        while ((i = is.read(inbuf, byteoff, inbuf.length-byteoff)) > 0) {
          byteoff += i;
          decompOffset += i;
          //Log.e("RIKAI","Read " + i + " bytes, byteoff="+byteoff+", decompOffset=" + decompOffset);
          if (byteoff == inbuf.length) {
            int outsz = compressBytes(inbuf,0,inbuf.length,outbuf);
            os.write(outbuf,0,outsz);
            offsets.add(new Long(decompOffset));
            offsets.add(new Long(os.getFilePointer()));
            byteoff=0;
          }
        }
        //Log.e("RIKAI","Escaped loop with byteoff="+byteoff+", decompOffset=" + decompOffset);
        if (byteoff != 0) {
          int outsz = compressBytes(inbuf,0,inbuf.length,outbuf);
          os.write(outbuf,0,outsz);
          offsets.add(new Long(decompOffset));
          offsets.add(new Long(os.getFilePointer()));
        }
        // at the end, we have a table of pairs of longs (decompOffset, compOffset) followed by
        // the length of that table (not including itself)
        offsets.add(new Long(offsets.size()));
        for (int j=0; j<offsets.size(); j++) {
    	    os.writeLong(offsets.elementAt(j));
        }
      } catch (IOException ioe) {
        System.out.println("Error while compressing: " + ioe);
      }
    } catch (FileNotFoundException e) {
    }
  }
}

